import Queue from '@/sources/Queue/useDcl';
import RB from './index'
import { RBNode } from './types'
import Assert from '@/utils/assets'
export const test = () => {
    const rb = new RB();

    // 添加
    // uncle不为空
    // const arr = [4, 8, 9] // RR型
    // const arr = [12, 14, 13] // RL型
    // const arr = [8, 4, 3] // LL型
    // const arr = [8, 4, 6] // LR型

    // uncle为空
    // const arr = [8, 4, 6, 9] // RR上溢 
    // const arr = [8, 4, 6, 7] // RL上溢 
    // const arr = [8, 4, 6, 3] // LL上溢 
    // const arr = [8, 4, 6, 5] // LR上溢 

    // 删除

    // 删除的是红色的节点
    // const arr = [21, 29, 71, 96, 56, 57, 90, 70]
    // rb.batchAdd(arr)
    // rb.remove(90)
    // print(rb)

    // 替换的节点是红色
    // const arr = [21, 29, 71, 96, 56, 57, 90, 70]
    // rb.batchAdd(arr);
    // rb.remove(96)
    // print(rb)

    // 兄弟节点是黑色，并且至少有一个红色子节点
    // （1）
    // const arr = [21, 29, 71, 96, 56, 57, 90, 70]
    // rb.batchAdd(arr)
    // rb.batchRemove(96, 90)
    // print(rb)
    // （2）
    // const arr = [21, 29, 71, 96, 56, 57, 90, 70]
    // rb.batchAdd(arr)
    // rb.remove(90)
    // rb.remove(70)
    // rb.remove(96)
    // print(rb)
    // （3）
    // const arr = [21, 29, 71, 96, 56, 57, 90, 70]
    // rb.batchAdd(arr)
    // rb.batchRemove([56, 90, 96])
    // print(rb)

    // （3）（删除左边的情况）
    const arr = [21, 29, 71, 96, 56, 57, 90, 70]
    rb.batchAdd(arr)
    rb.batchRemove([70, 21])
    print(rb)


    // 兄弟节点为黑色，没有一个红色子节点
    // const arr = [21, 29, 71, 96, 56, 57, 90, 70]
    // rb.batchAdd(arr);
    // // rb.remove(96)
    // rb.batchRemove([56, 70, 90])
    // rb.remove(96)
    // print(rb)


    // 兄弟节点是红色
    // const arr = [21, 29, 71, 96, 56, 57, 90, 70]
    // rb.batchAdd(arr);
    // print(rb)
    // rb.remove(21)
    // print(rb)


}
/**
 * 打印二叉树
 * @param rb 
 */
export const print = <T>(rb: RB<T>) => {
    // 是空的
    if (rb.isEmpty()) return;
    let root = rb.getRoot();
    const queue = new Queue<RBNode<T>>();
    queue.enQueue(root!);
    let levelSize = 1,
        height = 0;
    const hInfo: Record<string, Array<RBNode<T>>> = {
        l1: []
    }

    while (!queue.isEmpty()) {
        const node = queue.deQueue()!;
        levelSize--;
        if (node === root) {
            // str += `${node.value} \n`
            hInfo.l1.push(node!)
        }
        // parent = node;
        // 左节点
        if (node.left) {
            queue.enQueue(node.left)
        }
        // 右节点
        if (node.right) {
            queue.enQueue(node.right)
        }

        if (levelSize === 0) {
            // 该层已经访问过了
            // 此时在队列的都是下一层
            levelSize = queue.size();

            const tmp = height + 2;
            queue.forEach((ele) => {
                (hInfo['l' + (tmp)] || (hInfo['l' + (tmp)] = [])).push(ele!)
            })

            // 更新层数
            height++
        }
    }
    printRBTree(hInfo)
}


/**
 * 打印出二叉树
 * @param d 
 */
const printRBTree = (d: Record<string, any>) => {
    const keys = Object.keys(d),
        len = keys.length;
    // root偏移的距离
    const padLen = 8;

    // 记录层数
    let desc = 4;

    let str = ''

    for (let i = 0; i < len; i++) {
        const sub = d[keys[i]],
            len = sub.length;
        for (let j = 0; j < len; j++) {
            if (i === 0) {
                // 第一层
                sub[j].pad = padLen
                str += `${pad(padLen)}${sub[j].value}_c[${sub[j].color}]_p[${sub[j].parent?.value || 'null'}]`
            } else {
                // debugger
                // 不是第一层 
                const node = sub[j];
                // if (node.value === 15) debugger
                if (node.isLeft()) {
                    // 是左孩子
                    if (j === 0) {
                        // 该层第一个孩子
                        str += `${pad(node.parent.pad - desc) + sub[j].value}_c[${sub[j].color}]_p[${sub[j].parent.value}]`
                        node.pad = node.parent.pad - desc
                    } else {
                        // 上一个节点的pad
                        const tmp = sub[j - 1].pad + 8
                        str += `${pad(8) + sub[j].value}_c[${sub[j].color}]_p[${sub[j].parent.value}]`
                        node.pad = tmp
                    }

                } else {
                    // 是右孩子
                    if (j === 0) {
                        // 该层的第一个孩子
                        str += `${pad(node.parent.pad + desc) + sub[j].value}_c[${sub[j].color}]_p[${sub[j].parent.value}]`
                        node.pad = node.parent.pad + desc
                    } else {
                        // debugger
                        const tmp = sub[j - 1].pad + 8
                        str += `${pad(8) + sub[j].value}_c[${sub[j].color}]_p[${sub[j].parent.value}]`
                        node.pad = tmp
                    }
                }
            }
        }
        str += '\n'
    }

    console.log(str);
    // console.log('偏移:', pad(padLen).length)


}


/**
 * 填空
 * @param level 
 */
const pad = (level: number) => {
    return ''.padEnd(level, ' ')
}